% !TEX root = ../main.tex

\begin{abstract}
    深度学习编译器中，图替换是一类重要的计算图层次变换，方法是将模型计算图的一些子图替换成与之等效的子图。目前大部分编译器中，图替换程序通常是由开发人员手工编写。由于深度学习图替换规则数量多，且图替换具有较高的模型特异性，及时支持主流模型的替换需要较多工作量。一些编译器中支持通过领域特定语言来定义替换规则来减轻工作量，但也存在表达能力弱、开发效率低等不足。

    介绍了嵌入于Python中的声明式计算图替换语言——GSL，便于在深度学习编译器中定义新的计算图替换。在语言设计方面，提出了使用模式表达式表达模式图的结构、使用属性表达式表达算子属性约束的框架。该语言可以表达具有多输出顶点、可变模式的替换规则。在语言实现方面，提出了一种语言的执行模式，以及了一种高效的双向匹配算法，以支持多输出模式与可变输出模式的匹配。

    开展了相关实验对GSL进行评价。语言设计方面，使用GSL编写了TVM Relay中涉及的计算图替换，并与相关实现方式进行比较，体现了语言表达能力的增强以及对开发效率的提升。语言实现方面，对双向匹配算法进行测试，体现了其在时间复杂度上的高效性。
\end{abstract}

\begin{abstract*}
    In deep learning compilers, graph substitution is a kind of important graph-level transformation, which replaces some subgraphs of a computation graph with their equivalent counterparts. In most compilers, graph substitution programs are usually hand-coded by developers. Considering large number and high model-specificity of substitution rules, it means a lot of work to support substitutions in mainstream models in time. Some compilers support defining substitution rules through some domain-specific language to reduce work, but these languages may not be so expressive and efficient for development.

    We introduce a declarative computation graph substitution language - GSL, embedded in Python, for deep learning compiler users to define new graph substitutions. In terms of design, we devise a framework where pattern expression is used to express structure of pattern graph, and attribute expression to express constraints on operator attributes. This language can express substitution rules with multiple outputs or with variadic patterns. In terms of implementation, we devise a execution mode for the language, as well as an efficient bidirectional matching algorithm to support multiple output and variadic output patterns.

    We carry out experiments to evaluate GSL. For the design, we write substitutions involved in TVM Relay and compare it with related implementation methods, to demonstrate its improvement in expressivity and development efficiency. For implementation, we test the bidirectional matching algorithm to demonstrate its efficiency in time complexity.
\end{abstract*}
